package leetcode.p815;

import java.util.*;

/**
 * @author: trtan
 * @date: 2021-06-28 10:39
 **/
public class BusRoutes {
    /**
     * 题目要求的就是从起始站点到目标站点所最少经过的公交路线（即最小换乘次数）
     * n <= 500
     * routes[i].length <= 1e5
     * sum(routes[i]) <= 1e5
     * 那么此题就可以构建一个图，点为公交路线，边为各公交路线之间的到达关系，每条边需要的花费为1，最后从包含source的公交路线出发，bfs遍历到包含target的公交路线
     * 建图时，根据站点出现在不同的公交路线中，为这些公交路线建立边
     * 可以从遍历每条路线开始，用一个Map维护每个站点出现在哪些线路中，即每个站点维护一个集合，表示这些公交线路可以相互到达
     * 每次新遍历一条线路，根据出现的站点将新线路与集合中的线路建边
     * @param routes n行 每行代表一个公交路线 即[1, 3, 7]代表1->3->7-1这个路线
     * @param source 起始站点
     * @param target 目标站点
     * @return int
     * @author trtan
     * @date 2021/6/28 11:11
     */
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (target == source) {
            return 0;
        }
        int n = routes.length;
        boolean[][] edge = new boolean[n][n];
        Map<Integer, List<Integer>> map = new HashMap<>();
        // 遍历n条线路
        for (int i = 0; i < n; i++) {
            // 遍历当前线路的站点
            for (Integer t : routes[i]) {
                // 获取包含当前站点的线路
                List<Integer> list = map.getOrDefault(t, new ArrayList<>());
                // 建边
                for (Integer line : list) {
                    edge[i][line] = true;
                    edge[line][i] = true;
                }
                // 更新包含当前站点的线路
                list.add(i);
                map.put(t, list);
            }
        }
        Queue<Integer> que = new LinkedList<>();
        // 获取包含source站点的线路 从这些线路出发
        List<Integer> list = map.getOrDefault(source, new ArrayList<>());
        // dis代表花费
        int[] dis = new int[n];
        Arrays.fill(dis, -1);
        for (Integer line : list) {
            que.offer(line);
            dis[line] = 1;
        }
        // bfs遍历
        while (!que.isEmpty()) {
            Integer line = que.poll();
            for (int i = 0; i < n; i++) {
                // 判断当前线路是否被访问过，如果被访问过那花费不可能更低了， 如果没有就更新
                if (edge[line][i] && dis[i] == -1) {
                    dis[i] = dis[line] + 1;
                    que.offer(i);
                }
            }
        }
        int min = Integer.MAX_VALUE;
        // 从包含target的线路中寻找最小花费
        for (Integer line : map.getOrDefault(target, new ArrayList<>())) {
            if (dis[line] != -1) {
                min = Math.min(min, dis[line]);
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}
